from typing import List


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def getKthElement(k):
            idx1, idx2 = 0, 0
            while True:
                if idx1 == m:
                    return nums2[idx2 + k - 1]
                if idx2 == n:
                    return nums1[idx1 + k - 1]
                if k == 1:
                    return min(nums1[idx1], nums2[idx2])
                newIdx1 = min(idx1 + k // 2 - 1, m - 1)
                newIdx2 = min(idx2 + k // 2 - 1, n - 1)
                pivot1, pivot2 = nums1[newIdx1], nums2[newIdx2]
                if pivot1 <= pivot2:
                    # 删掉nums1至少一半半内容
                    k -= newIdx1 - idx1 + 1
                    idx1 = newIdx1 + 1
                else:
                    k -= newIdx2 - idx2 + 1
                    idx2 = newIdx2 + 1

        m, n = len(nums1), len(nums2)
        totalLength = m + n
        if (totalLength % 2 == 1):
            return getKthElement((totalLength + 1) // 2)
        else:
            return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2
